package learn.sort;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Date;

/**
 * @author 于昂
 * Date 2021/1/7
 * Time 21:06
 */
public class BubbleSort {
    public static void main(String[] args) {
//        base();
//        int[] array = {3, 9, -1, 10, -2};
//        bubbleSort(array);

        //测试一下冒泡排序的效率
        //事前判断O(n) = n^2
        int[] array2 = new int[800];
        for (int i = 0; i < array2.length; i++) {
            array2[i] = (int) (Math.random() * 800000);
        }

        // 放在要检测的代码段前，取开始前的时间戳
        Long startTime = System.currentTimeMillis();
        bubbleSort(array2);
        // 放在要检测的代码段后，取结束后的时间戳
        Long endTime = System.currentTimeMillis();

        // 计算并打印耗时
        long tempTime = (endTime - startTime);
        System.out.println("花费时间：" +
                (((tempTime / 86400000) > 0) ? ((tempTime / 86400000) + "d") : "") +
                ((((tempTime / 86400000) > 0) || ((tempTime % 86400000 / 3600000) > 0)) ? ((tempTime % 86400000 / 3600000) + "h") : ("")) +
                ((((tempTime / 3600000) > 0) || ((tempTime % 3600000 / 60000) > 0)) ? ((tempTime % 3600000 / 60000) + "m") : ("")) +
                ((((tempTime / 60000) > 0) || ((tempTime % 60000 / 1000) > 0)) ? ((tempTime % 60000 / 1000) + "s") : ("")) +
                ((tempTime % 1000) + "ms"));

    }

    private static void bubbleSort(int[] array) {
        int temp = 0;
        boolean flag = false;
        for (int i = 0; i < array.length - 1; i++) {//这里i的可选值为 0 1 2 3
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    flag = true;//发送过交换
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }

            if (!flag) { //一次循环中没有发生交换
                break;
            } else {//交换过，置为false
                flag = false;
            }
//            System.out.println(Arrays.toString(array));
        }
    }

    private static void base() {
        int[] array = {3, 9, -1, 10, -2};
        //理解 冒泡排序的演变过程
        int temp = 0;
        for (int i = 0; i < array.length - 1; i++) { //循环截止条件为array.length - 1 -0
            if (array[i] > array[i + 1]) {
                temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
        System.out.println(Arrays.toString(array));

        for (int i = 0; i < array.length - 2; i++) { //循环截止条件为array.length - 1 -1
            if (array[i] > array[i + 1]) {
                temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
        System.out.println(Arrays.toString(array));

        for (int i = 0; i < array.length - 3; i++) { //循环截止条件为array.length - 1 -2
            if (array[i] > array[i + 1]) {
                temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
        System.out.println(Arrays.toString(array));

        for (int i = 0; i < array.length - 4; i++) {//循环截止条件为array.length - 1 -3
            if (array[i] > array[i + 1]) {
                temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
        System.out.println(Arrays.toString(array));
    }
}
